package leetcode.editor.cn;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 单词拆分
 * @author qulq
 * @date 2024-07-11 21:46:29
 */
public class T139_WordBreak{
	 public static void main(String[] args) {
	 	 // 测试代码
		 Solution solution = new T139_WordBreak().new Solution();
		 System.out.println("leetcode".substring(0, 7));
	 }

	/**
	 * 最后一步：最后一位i， 前面的0-j可以被拆分，j+1到i又在字典中
	 * 因为第一位可能在、可能不在，如果f[i]表示下标，则初始化f[0]的时候需要分开讨论在和不在两种情况
	 * 所以采用序列型的方式，f[i]表示前i位是否能被拆分
	 */
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

		// dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被拆分
		// dp[i]=dp[j] && check(s[j..i−1])    0 <= j <= i
		Set<String> set = new HashSet<>(wordDict);
		boolean[] dp = new boolean[s.length() + 1];
		dp[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < i; j++) {
				if (dp[j] && set.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}